/**
 * 希尔排序算法，也称增强版本插入排序算法，时间复杂度在O(nlgn)和O(n^2)之间 
 * @author firebroo
 *
 */
public class ShellSort {  
    public static void shellSort(int[] data) {  
        int j = 0;  
        int temp = 0;                                                               //临时存放待插入已经排序好的序列的元素
        for (int increment = data.length / 2; increment > 0; increment /= 2) {      //排序使用的增量,第一次为数组长度的一半
            for (int i = increment; i < data.length; i++) {                         //按照增量将数组拆分成n个子数组，对子数组分别进行插入排序  
                temp = data[i];  
                for (j = i; j >= increment; j -= increment) {                       
                    if(temp < data[j - increment]){  								                //如果待插入元素小于已经排序好的最后一个元素，则把最后一个元素后移一位,继续和前一个元素比较
                        data[j] = data[j - increment];  
                    }else{                                                          //如果待插入元素大于已经排序好的最后一个元素，跳出循坏，直接插入
                        break;  
                    }  
                }   
                data[j] = temp;                                                     //将临时变量的元素插入正确位置
            }  
        }  
    }  
  
    /**
     * 希尔排序测试
     * @param args
     */
    public static void main(String[] args) {  
    	int[] data={12,2,43,3,34,5,6};
        shellSort(data);  
        for (int i = 0; i < data.length; i++)  
        	System.out.println(data[i]);
    }  
}  
